package com.learn.acm.three;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * 有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
 *
 * 现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
 *
 * 求所能获得硬币的最大数量。
 *
 * 说明:
 *
 * 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
 * 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
 * 示例:
 *
 * 输入: [3,1,5,8]
 * 输出: 167
 * 解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
 *      coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
 *
 * 输入: [3,1,1,5,8]
 * 输出: 167
 * 解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
 *      coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
 *
 * [3,1,5,1,2,1,8,1]
 */
public class Solution312 {


    public int maxCoins(int[] nums) {
        if (null == nums || nums.length <= 0) return 0;

        List<Integer> numsList = new LinkedList<Integer>();
        for (int i : nums) {
            numsList.add(i);
        }
        int sum = 0;
        int minArea = 0,max=Integer.MIN_VALUE;
        while (numsList.size() > 0) {
            for (int i = 0;i<numsList.size();i++) {
                int minAreaLeft = minArea-1 < 0 ? 1 : numsList.get(minArea-1);
                int minAreaRight = minArea+1 >= numsList.size() ? 1 : numsList.get(minArea+1);
                max = minAreaLeft * numsList.get(minArea) * minAreaRight;
                int nowLeft = i == 0 ? 1 : numsList.get(i-1);
                int nowRight = i == numsList.size()-1 ? 1 : numsList.get(i+1);
                int nowMax = nowLeft * numsList.get(i) * nowRight;
                if (numsList.get(minArea) == numsList.get(i)) {
                    if (nowMax > max) {
                        max = nowMax;
                        minArea = i;
                        continue;
                    }
                } else if (numsList.get(minArea) > numsList.get(i)) {
                    minArea = i;
                    max = nowMax;
                }
            }
            sum += max;
            numsList.remove(minArea);
        }
        return sum;
    }


    @Test
    public void test312() {
        int[] a = new int[]{3,1,5,8};

        System.out.println(maxCoins(a));

    }
}
